package com.njupt.graphTheory;

import lombok.val;

import java.util.*;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/4/17 20:33
 * @Description: dijkstra 基于邻接表的堆优化版
 * @Version: 1.0
 */


//记录minDest数组中距离源点的节点，以及该节点到源点的距离，我们把这个数值放入一个优先级队列中
class Pair<U,V>{
    public U first;  //当前节点

    public V dest;   //当前节点到源点的距离

    public Pair(U first,V dest){
        this.first = first;
        this.dest = dest;
    }
}


class Edge{
    int to;   //邻接的顶点
    int val;  //边的权值

    public Edge(int to,int val){
        this.to = to;
        this.val = val;
    }
}
public class KaMaDijkstraPlus_47 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        int M = sc.nextInt();

        List<List<Edge>> graph = new ArrayList<>(N + 1);
        for(int i = 0;i<= N;i++){
            graph.add(new ArrayList<>());
        }


        //构建邻接矩阵
        for (int i = 0; i < M; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int val = sc.nextInt();
            graph.get(from).add(new Edge(to,val));
        }

        int start = 1;
        int end = N;

        int[] minDest = new int[N + 1];
        Arrays.fill(minDest,Integer.MAX_VALUE);
        minDest[start] = 0;

        boolean[] isVisited = new boolean[N + 1];


        PriorityQueue<Pair<Integer, Integer>> ppPairs = new PriorityQueue<>((pair1,pair2) ->{
            return pair1.dest - pair2.dest;
        });
        ppPairs.add(new Pair<>(start,0));

        dijkstra(graph,end,minDest,isVisited,ppPairs);

        if(minDest[end] == Integer.MAX_VALUE){
            System.out.println(-1);
        }else {
            System.out.println(minDest[end]);
        }
    }

    private static void dijkstra(List<List<Edge>> graph, int n, int[] minDest, boolean[] isVisited, PriorityQueue<Pair<Integer, Integer>> ppPairs) {
        while(!ppPairs.isEmpty()){
            Pair<Integer, Integer> curSource = ppPairs.poll();
            //TODO
            if(isVisited[curSource.first]){
                continue;
            }

            isVisited[curSource.first] = true;

            for(Edge edge : graph.get(curSource.first)){
                if( !isVisited[edge.to]){
                    if(minDest[curSource.first] + edge.val < minDest[edge.to]){
                        minDest[edge.to] = minDest[curSource.first] + edge.val;
                        ppPairs.add(new Pair<Integer,Integer>(edge.to, minDest[edge.to]));
                    }
                }
            }
        }

    }


}
